package 算法模板;

import java.util.Arrays;

/**
 * 思路:
 * 快速选择算法可以看作是快速排序算法的“一半”。快速排序算法可以得出整个序列的大小顺序，但
 * 是，现在我只想知道第k小的元素是什么，其余的不关心。求第k小的元素而把整个序列排序又太过
 * 小题大作。
 * 那么，现在进行的是快速排序算法，假设我选取的枢纽元是p。
 * 在双指针交换元素之后，[ l, j ]区间是全部小于p的元素， [ j + 1, r ]区间是全部大于p的元素。
 * 若此时 k 小于等于 j指针 ，说明答案只会在 [ l, j ] 之间。若此时k 大于 j指针，说明答案只会
 * 在[ j + 1, r]之间。则另外的区间就不必进行递归处理了，因为答案肯定不在里面，处理了也是做的
 * 无意义的花费。
 * <p>
 * 应用场景:
 * 求一个序列中的第 k大 或者 第 k 小的值
 */
public class 快速选择 {

    public static void main(String[] args) {

        int[] nums = {5, 3, 1, 2, 4, -1, 6, 7, 8};
        System.out.println(new 快速选择().findKthLargest(nums, 9));
        System.out.println(Arrays.toString(nums));

    }

    public int findKthLargest(int[] nums, int k) {
        // [2,1,4,3] ，注意，如果是寻找第 1 大的元素，那么应该是排序之后的数组中的 4
        return fastSelect(0, nums.length - 1, nums, nums.length - k + 1);
    }

    public Integer fastSelect(int left, int right, int[] nums, int k) {
        if (left == right && left + 1 == k) {
            return nums[left];
        }
        if (left >= right) {
            return null;
        }
        int key = nums[left], l = left - 1, r = right + 1;
        // 双指针交换左边 >= key 右边 <=key 的元素
        while (l < r) {  // l==r 代表着 这个位置已经排序好
            while (nums[++l] < key) ;
            while (nums[--r] > key) ;
            if (l < r) {
                replace(l, r, nums);
            }
        }
        // 虽然一轮排序之后，nums[keyIdx] 不一定等于 key，
        // 但是key排序之后最终的位置一定是在 keyIdx 的索引位置
        // [keyIdx,right] 中的元素一定都是 >= key 的
        int keyIdx = r == l ? r : r + 1;
        if (keyIdx + 1 == k) {  // l 是索引，需要+1
            return key;
        } else if (keyIdx + 1 > k) {  //
            return fastSelect(left, keyIdx - 1, nums, k);
        } else {
            // 当 r==l 时，keyIdx 的位置一定不是 k，需要跳过 keyIdx，不然死循环
            return fastSelect(r == l ? keyIdx + 1 : keyIdx, right, nums, k);
        }
    }

    private void replace(int l, int r, int[] nums) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

}
